MOD = 10 ** 9 + 7


class Solution:
    def distinctSubseqII(self, s: str) -> int:
        nums = [0] * 26
        now = 1
        for i, ch in enumerate(s):
            minus = nums[ord(ch) - 97]
            nums[ord(ch) - 97] = now
            # 当从上一次出现这个字母开始，到这一次出现这个字母之前，一个都没选中时，效果一样
            now = (now * 2 - minus) % MOD
        return now - 1


if __name__ == "__main__":
    print(Solution().distinctSubseqII("abc"))  # 7
    print(Solution().distinctSubseqII("aba"))  # 6
    print(Solution().distinctSubseqII("aaa"))  # 3
